The present invention relates to the encryption of digital messages so as to maintain privacy of their contents when the resulting encrypted messages are transmitted over insecure channels, i.e., in such a way as to be subject to interception by unauthorized parties. The need for practical means to maintain privacy of digital messages has become urgent in the wake of the rapid expansion of digital networks in which a wide variety of users share the same communications resources whose transmissions must be considered subject to unauthorized interception. The messages that must be effectively transmitted through such a network may include banking data, medical data, personnel files, electronic mail, documents, images for teleconferencing, credit information and similar material whose sensitivity demands that it be kept private.
The conventional cryptographic solution to the problem of maintaining the privacy of a digital message requires the prior possession of a common secret key, used to both encrypt and decrypt messages, by those parties who wish to exchange private messages among them. The paper "Communication Theory of Secrecy Systems" by C. E. Shannon, Bell System Tech. J., Vol. 28, pp. 656-715, October 1949, gives a summary of this conventional cryptographic approach and shows that perfect privacy can be achieved only when there are at least as many binary digits of secret key as there are bits of information in all the private messages that will be coded before the secret key is again changed. The secret key must of course be distributed to the authorized parties by some means not subject to unauthorized interception, for instance by certified couriers. The practical difficulties of generating, distributing and safeguarding large amounts of secret key render conventional cryptographic techniques of doubtful practical value as means for maintaining privacy of messages in large digital networks.
In the paper "New Directions in Cryptography" by W. Diffie and M. E. Hellman, IEEE Trans. Info. Th., Vol. IT-22, pp. 644-654, November 1976, alternative cryptographic approaches were proposed to eliminate the need to exchange secret keys. These approaches rely for their security entirely on the computational difficulty of the task that a cryptanalyst must perform in order to determine the private messages from their coded versions. These approaches, in contrast to the prior exchange of secret keys, require the prior exchange of public keys, that is, keys whose identity need not be kept secret but which must be available to any two users who wish to send secret messages between them. The public key is utilized in encrypting the message. A private key, known only to the receiver, and which is related to the public key in a manner which makes it determination mathematically difficult, is then utilized to decrypt the public message. One object of the invention is to provide a technique for maintaining privacy of digital messages that requires no prior distribution of any key, whether public or private.